#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*
 *
 *在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。



示例 1:

输入: [7,5,6,4]
输出: 5


限制：

0 <= 数组长度 <= 50000
 *
 *
 *
 * */
//暴力搜索直接超时  这个使用排序 归并排序 如果前半部分大于后半部分计数++
//想出这个办法的人应该是对归并排序有很深入的了解 为啥我感觉他们会重复啊
// 因为得搞数组进行归并 low到mid mid+1到high 所以咱们把mid 传入进去
int count = 0;

void merge(vector<int> &nums, int low, int high, int mid) {
    //还是区间这里出错 了 需要多加练习
    vector<int> left(nums.begin() + low, nums.begin() + mid + 1);//区间内另一个数组的元素到vector中,注意最后面的end其实并不包括 其实后面就是一个长度

    vector<int> right(nums.begin() + mid + 1, nums.begin() + 1 + high);
    int i = 0, j = 0;
    int index = low;
    while (i < left.size() && j < right.size()) {
        //这个题还有一个坑 我没写等号 ...擦写了也不对
        if (left[i] <= right[j]) {
            //count+=i;//获取j前面元素个数
            nums[index++] = left[i++];
        } else {


            ///5 7    4  6
            //当左边数组的大与右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，
            //mid -low +1算出区间长度 -i 例如 57 46 如果4<5 则一定有 4<5 后面的数 因此只要求 left.size()-i当前位置
            count += mid - i - low + 1;//妈蛋这个搞了一个小时了吧
            nums[index++] = right[j++];

        }

    }

    while (i < left.size()) {
        nums[index++] = left[i++];
        //  count++;
    }
    while (j < right.size()) {
        nums[index++] = right[j++];
    }

}

void merge_sort(vector<int> &nums, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;

        merge_sort(nums, low, mid);
        merge_sort(nums, mid + 1, high);
        merge(nums, low, high, mid);
    }
}


int reversePairs(vector<int> &nums) {

    merge_sort(nums, 0, nums.size() - 1);

    return count;


}